package com.demo.java.OD501_550.OD506;

import java.util.Scanner;
import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【代表团坐车(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146477299
 */
public class OdMain {
    public static int count = 0;

    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        int[] nums = Arrays.stream(in.nextLine().split(","))
                .mapToInt(Integer::parseInt)
                .toArray();  // 输入代驾团队的成员数

        int target = Integer.parseInt(in.nextLine());  // 目标汽车数

        // 使用回溯算法寻找最少汽车数
        System.out.println(findTargetSumWays(nums, target));
        return;
    }

    public static int findTargetSumWays(int[] nums, int target) {
        backtrack(nums, target, 0, 0);
        return count;
    }

    public static void backtrack(int[] nums, int target, int index, int sum) {
        if (index == nums.length) {  // 判断是否已遍历完所有团队
            if (sum == target) {  // 如果总车辆数达成目标
                count++;
            }
        } else {
            backtrack(nums, target, index + 1, sum + nums[index]);  // 尝试当前团队使用一个车
            backtrack(nums, target, index + 1, sum);  // 跳过当前团队
        }
    }
}